import java.util.PriorityQueue;
import java.util.Comparator;
/*
题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，
那么中位数就是所有数值排序之后位于中间的数值。
如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
思路：
考虑到AVL实现时间较长
使用大根堆和小根堆实现,最大、最小堆可以使用优先队列、
*/
public class Solution {
    int count = -1;
    PriorityQueue<Integer>smallNode = new PriorityQueue<>();
    PriorityQueue<Integer> bigNode = new PriorityQueue<>(10 ,new Comparator<Integer>() {
        public int compare(Integer i1, Integer i2) {
            return i2 - i1;
        }
    });


    public void Insert(Integer num) {
        count++;
        if(count%2==0){//偶数，计划插入小根堆
            if(bigNode.isEmpty()){
                smallNode.add(num);
            }else{
                if(num<bigNode.peek()){
                    bigNode.add(num);
                    smallNode.add(bigNode.poll());
                }
                else{
                    smallNode.add(num);
                }
            }
        }
        else{
            if(smallNode.isEmpty()){
                bigNode.add(num);
            }else{
                if(smallNode.peek()<num){
                    smallNode.add(num);
                    bigNode.add(smallNode.poll());
                }
                else
                    bigNode.add(num);
            }
        }

    }

    public Double GetMedian() {
        if((count+1)%2!=0){
            return (double)(smallNode.peek());
        }else{
            return ((double)bigNode.peek() + (double)smallNode.peek())/2;
        }
    }

    public static void main(String args[]){
        Solution s = new Solution();

        for(int i=0;i<5;i++){
            s.Insert(i);
        }


        double a = s.GetMedian();


        System.out.println("hah");

    }

}